package cn.xkai.structure;

/**
 * @description: 设计链表
 * @author: kaixiang
 * @date: 2022/7/23
 **/
class MyLinkedList {
    static class Node {
        int val;
        Node next;

        Node(int val) {
            this.val = val;
        }
    }

    int size;
    Node head;

    /**
     * 构造函数
     */
    public MyLinkedList() {
        //初始化
        this.size = 0;
        this.head = null;
    }

    /**
     * 获取指定节点
     */
    public int get(int index) {
        if (index < 0 || index >= size || head == null) {
            return -1;
        }
        //头节点开始遍历找到指定节点(这里就体现查询慢)
        Node node = this.head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.val;
    }

    /**
     * 头插法
     */
    public void addAtHead(int val) {
        //新建节点
        Node node = new Node(val);
        //把原头节点放到新节点下一个
        node.next = this.head;
        //把新节点设置为头节点
        this.head = node;
        //长度加1
        size++;
    }

    /**
     * 尾插法
     */
    public void addAtTail(int val) {
        if (size == 0) {
            this.head = new Node(val);
            head.next = null;
            size++;
        } else {
            //尾插法是效率最低的场景，需完全遍历整个链表
            Node node = this.head;
            while (node.next != null) {
                node = node.next;
            }
            Node tail = new Node(val);
            tail.next = null;
            node.next = tail;
            size++;
        }
    }

    /**
     * 指定位置新增节点
     */
    public void addAtIndex(int index, int val) {
        if (index > this.size) {
            return;
        }
        if (index <= 0) {
            addAtHead(val);
            return;
        }
        if (index == this.size) {
            addAtTail(val);
            return;
        }
        //找到指定位置
        Node node = this.head;
        for (int i = 0; i < index - 1; i++) {
            node = node.next;
        }
        //O(1)的体现
        Node newNode = new Node(val);
        newNode.next = node.next;
        node.next = newNode;
        size++;
    }

    /**
     * 删除指定节点
     */
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= this.size) {
            return;
        }
        if (index == 0) {
            if (size != 1) {
                Node temp = this.head.next;
                this.head = temp;
                size--;
                return;
            } else {
                this.head = null;
                size--;
                return;
            }
        }
        //找到指定位置
        Node node = this.head;
        for (int i = 0; i < index - 1; i++) {
            node = node.next;
        }
        //O(1)的体现
        Node deleteNode = node.next;
        node.next = deleteNode.next;
        size--;
    }
}
/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
